package dp.integerBreak;
/**
 * @Date 2020/04/19
 * @author 王光浩
 * @Thinking 使用DP
 * 	状态转移方程： f(k) = Math.max( i* Math.max(k-i,f(k-i)) ) ,其中 0<i<K 
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodTwo {
	public int integerBreak(int n) {
		int[] helper = new int[n+1];
		helper[1] = 1;
		for(int i=2 ; i<=n ; i++) {
			int max = 0;
			for(int j=1 ; j<i ; j++) {
				int tem = Math.max(i-j,helper[i-j] );
				max = Math.max(max, j*tem);
			}
			helper[i] = max;
		}
		return helper[n];
    }
}
